#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int begin;
    int end;
    int len;
    int _n;
public:
    string longestPalindrome(string s)
    {
        int left, right;
        begin = end = 0, _n = s.size();
        for (int i = 0; i < _n; i++)
        {
            left = right = i;
            if (right + 1 < _n && s[i] == s[right + 1]) {
                CenterExtent(s, left, right + 1);
            }

            if (left - 1 >= 0 && s[i] == s[left - 1]) {
                CenterExtent(s, left - 1, right);
            }

            if (right + 1 < _n && left - 1 >= 0 && s[left - 1] == s[right + 1]) {
                CenterExtent(s, left - 1, right + 1);
            }
        }
        printf("begin:%d, end:%d\n", begin, end);
        return s.substr(begin, end - begin + 1);
    }

    void CenterExtent(const string& s, int left, int right)
    {
        while (left > 0 && right < _n)
        {
            if (left == 0)
                break;
            if (right == _n - 1)
                break;

            if (s[left - 1] == s[right + 1])
            {
                left--;
                right++;
            }
            else
            {
                break;
            }
        }
        if (right - left > end - begin) {
            begin = left;
            end = right;
        }
    }
};

int main1()
{
    Solution sol;
    sol.longestPalindrome("ccc");

    return 0;
}